#include<bits/stdc++.h>
using namespace std;

//坑点:
/*
	1. 插入的时候沿途的pass要++ 插入字符串结尾的end也要++
	2.查询是否有字符串word的时候 最后不能直接返回true  而是要返回该字符串结尾节点的end的值是否大于0
	3.往下走的时候 记得迭代cur的位置 cur = cur->nexts[path]
	4.计算下一个位置的时候 使用的是str[i] - 'a'  不是str[i] - '0' !!!   
	5.删除字符串的时候要先查找该字符串是否真的存在  删除的时候需要同步更新pass和end
*/
struct Node
{
	Node()
	{
		nexts.resize(26,nullptr);
		end = 0;
		pass = 0;
	}
	~Node()
	{
		for(auto& node:nexts)
		{
			delete node;
			node = nullptr;
		}
	}
	vector<Node*> nexts;
	int end;
	int pass;
};
class Trie
{
public:
	Trie()
	{
		root = new Node();
	}
	~Trie()
	{
		delete root;
		root = nullptr;
	}
	void insert(string str)
	{
		if(str == "")
			return ;
		Node* cur = root;
		int path = 0;
		cur->pass++;
		for(int i = 0;i<str.size();i++)
		{
			path = str[i] - 'a';
			if(cur->nexts[path] == nullptr)
			{
				cur->nexts[path] = new Node();
			}
			cur = cur->nexts[path];
			cur->pass++;
		}
		cur->end++;
	}
	
	bool search(string str)
	{
		if(str == "")
			return false;
		Node* cur = root;
		int path = 0;
		for(int i = 0;i<str.size();i++)
		{
			path = str[i] - 'a';
			if(cur->nexts[path] == nullptr)
			{
				return false;
			}
			cur = cur->nexts[path];
		}
		
		return cur->end > 0;
	}
	
	int prefixNumber(string str)
	{
		if(str == "")
			return 0;
		Node* cur = root;
		int path = 0;
		for(int i = 0;i<str.size();i++)
		{	
			path = str[i] - 'a';
			if(cur->nexts[path] == nullptr)
				return 0;
			cur = cur->nexts[path];
		}	
		return cur->pass;
	}
	
	int searchTimes(string str)
	{
		if(str == "")
			return 0;
		Node* cur = root;
		int path = 0;
		for(int i = 0;i<str.size();i++)
		{	
			path = str[i] - 'a';
			if(cur->nexts[path] == nullptr)
				return 0;
			cur = cur->nexts[path];
		}	
		return cur->end;
	}
	
	void _deleteString(string str,Node* cur,int index)
	{
		if(index == str.size())  return ;
			
		int path = str[index] - 'a';
		_deleteString(str,cur->nexts[path],index+1);
		delete cur->nexts[path];
		cur->nexts[path] = nullptr;
	}
	void deleteString(string str)
	{
		if(str == "")
			return ;
		if(search(str))
		{
			int path = 0;
			Node* cur = root;
			cur->pass--;
			for(int i = 0;i<str.size();i++)
			{
				path = str[i] - 'a';
				if(--cur->nexts[path]->pass == 0)
				{
					_deleteString(str,cur->nexts[path],i); //把该字符串当中cur->nexts[path]节点沿途往后的内容都删了
					delete cur->nexts[path]; //当前该节点也要删除
					cur->nexts[path] = nullptr;
					cur->end--; 
					return ;
				}
				cur = cur->nexts[path];
			}
			cur->end--;
		}
	}
	Node* root;
};


